// 小根堆
/*
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto& num: nums) {
            pq.emplace(num * num);
        }
        
        vector<int> ret;
        while(!pq.empty()) {
            ret.emplace_back(pq.top());
            pq.pop();
        }
        return ret;
    }
};
*/

// 归并排序
/*
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i = 0, j = nums.size() - 1, k;
        while (i <= j) {
            k = i + (j - i) / 2;
            if (nums[k] < 0) {
                i = k + 1;
            }
            else {
                j = k - 1;
            }
        }

        vector<int> ret;
        int n1 = i - 1, n2 = i;
        while (n1 >= 0 || n2 < nums.size()) {
            if (n2 == nums.size() || n1 != -1 && -nums[n1] < nums[n2]) {
                ret.push_back(nums[n1] * nums[n1]);
                n1--;
            }
            else {
                ret.push_back(nums[n2] * nums[n2]);
                n2++;
            }
        }
        return ret;
    }
};
*/

// 双指针
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        vector<int> ret;
        while (left <= right) {
            if (nums[left] * nums[left] < nums[right] * nums[right]) {
                ret.push_back(nums[right] * nums[right]);
                right--;
            }
            else {
                ret.push_back(nums[left] * nums[left]);
                left++;
            }
        }
        
        reverse(ret.begin(), ret.end());
        return ret;
    }
};